home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / List / Base_List.h < prev    next >
Text File  |  1992-06-18  |  18KB  |  381 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MJF 03/27/89 -- Initial design and implementation
  13. // Updated: MJF 04/15/89 -- Implemented Base list class.
  14. // Updated: MJF 06/01/89 -- Added const to member function arguments.
  15. // Updated: JCB 06/05/89 -- Fixed sort and merge.
  16. // Updated: JCB 06/20/89 -- Added protected slot, traversal, for use by
  17. //                          next_lunion, next_intersection, etc.
  18. //                          Modified reset() to initialize traversal flag.
  19. // Updated: MJF 06/21/89 -- Changed return types from List& to void or Boolean.
  20. // Updated: LGO 07/03/89 -- Inherit from Generic
  21. // Updated: MJF 08/10/89 -- Changed return values of operator+= etc to List ref
  22. // Updated: LGO 09/07/89 -- Make base-list constructor and destructor inline.
  23. // Updated: MBN 09/20/89 -- Added conditional exception handling
  24. // Updated: MBN 10/10/89 -- Added current_position() method for Iterator<Type>
  25. // Updated: MBN 10/11/89 -- Changed "current_position" to "curpos" and also
  26. //                          "previous_position" to "prevpos"
  27. // Updated: LGO 10/18/89 -- Get rid of the value method.
  28. // Updated: LGO 12/04/89 -- Make binary set operators not inline
  29. // Updated: VDN 02/21/92 -- New lite version
  30. //
  31. // A list is simply  made up of a collection  of nodes.   Each node contains  a
  32. // reference  count,  a pointer to  the next  node  in  the  list, and the data
  33. // object.
  34. //
  35. //                      +--------+         +--------+         +--------+
  36. //                      | Ref=2  |         | Ref=1  |         | Ref=2  |
  37. //    +-------+         +--------+         +--------+         +--------+
  38. //    | CoolList--+---+---->| Next --+-------->| Next --+----+--->| Next 0 |
  39. //    +-------+   |     +--------+         +--------+    |    +--------+
  40. //                |     | Data   |         | Data   |    |    | Data   |
  41. //                |     +--------+         +--------+    |    +--------+
  42. //                |                                      |
  43. //    +-------+   |                          +-------+   |
  44. //    | CoolList--+                          | CoolList--+
  45. //    +-------+                              +-------+
  46. //
  47. // The CoolList class is implemented with parameterized types. The specific type of
  48. // the elements in the list is  left  as a  parameter for  the user.  Each list
  49. // declared for elements of a different type  would be a  new class.  A list of
  50. // ints,   CoolList<int>, would expand   to a class  CoolList_int  and  a list strings,
  51. // CoolList<char*>, would expand  to a class CoolList_charp.  Note  that  the lists are
  52. // homogeneous lists where each element of the list is of  the same known type.
  53. // A heterogeneous list  could be maintained  by having the type  be void* or a
  54. // Generic object type where the type of the actual data could be determined.
  55. //
  56. // The CoolList class private data consists of a pointer to a Node class.  The Node
  57. // class contains a reference count, the data object, and a pointer to the next
  58. // node.   The data in each node  of a  list is an object of  type "Type".  The
  59. // CoolList  class is   derived from a  Base  CoolList class.  This file  contains  the
  60. // implementation  of the Base   CoolList  class.  The  CoolList  class can be found in
  61. // List.h
  62. //
  63. // The Base_List class implements the  generic list functionality.  This class
  64. // is not usable as a standalone class, but rather is designed to be derived by
  65. // the CoolList  class.   By providing generic operations   in  a base   class, the
  66. // quantity of code generated for each implementation of the parameterized CoolList
  67. // class is reduced considerably.
  68. //
  69. // All list nodes are  created dynamically and  mangaged with reference counts.
  70. // In the node object,  the reference count  value indicates the number of list
  71. // or node objects pointing to it.  When the value is zero the node  object and
  72. // its data will  be freed.  The  reference count technique  is  used to ensure
  73. // that the node and  its data gets  deallocated  when  the  node is  no longer
  74. // referenced.
  75. //
  76. // The Node class was introduced in order  to maintain the reference count from
  77. // each data  item in  the  list.  The CoolList  class  could have been implemented
  78. // without a pointer to a Node and instead contain a pointer to  the data and a
  79. // pointer to  the next list   item.   However, with  a reference  count it  is
  80. // necessary to have a separate class.  Consider the following set of lists and
  81. // sublists.  Both  List1 and List2  point to  (Node 1,  Node2,  Node3, Node4),
  82. // List3 is a sublist pointing to (Node3,  Node4),  and List4 points to (Node5,
  83. // Node3, Node4).  The  reference count totals for  each node  are shown in the
  84. // ().  Without a separate  node for each data item,  it would be  difficult to
  85. // determine when to deallocate the data when it is no longer referenced.
  86. //
  87. //  +-------+
  88. //  | List1 |---+
  89. //  +-------+   |
  90. //              |
  91. //              |
  92. //              |     +-------+     +-------+     +-------+     +-------+
  93. //              |     |       |     |       |     |       |     |       |
  94. //              +---->| Node1 |---->| Node2 |---->| Node3 |---->| Node4 |---->0
  95. //              |     |  (2)  |     |  (1)  |     |  (3)  |     |  (1)  |
  96. //              |     +-------+     +-------+     +-------+     +-------+
  97. //              |                                     ^
  98. //              |                   +-------+         |   
  99. //  +-------+   |                   | List3 |-------->+
  100. //  | List2 |---+                   +-------+         ^
  101. //  +-------+                                         |
  102. //                                        +-------+   |
  103. //                          +-------+     |       |   |
  104. //                          | List4 |---->| Node5 |---+
  105. //                          +-------+     |  (1)  |
  106. //                                        +-------+
  107. //
  108. // Note that because we have chosen to have a CoolList be comprised of Nodes, it is
  109. // not possible to have generic operations that will  scan a tree  comprised of
  110. // Nodes  themselves containing CoolLists.   This  manifestation is unfortunate but
  111. // necessary to implement heterogenous lists and the reference count scheme.
  112. //
  113. // There   are several constructors available for   the CoolList class.  The CoolList()
  114. // constructor creates a null list,  setting the  node  pointer to  zero.   The
  115. // CoolList(Type& a) constructor creates a list with one data node; a head value of
  116. // a  and a nil  tail.  The CoolList(Type& a,  CoolList& b) constructor creates  a list
  117. // with a head value of a and a b  as the tail.   The CoolList(CoolList& l) constructor
  118. // creates a new list whose head node points to the same node as list l.
  119. //
  120. // The supported operations in the CoolList  class are mirrored closely after those
  121. // in Common Lisp.  There are operations  which return the nth  tail of a list;
  122. // the sublist starting at the nth last node of a list; and  all but the n last
  123. // nodes of a list.  There are operations which return the length of  the list;
  124. // get or set the nth element of the  list; return the  position of a specified
  125. // element; test if the list is empty; clear a list; and test if  two lists are
  126. // equal.   There are  also operations  to search  for  a  specified  member or
  127. // sublist within a list; to reverse the list;  to copy the list; to  append or
  128. // prepend an element or sublist; to set  the tail of  the list; to replace all
  129. // or the first occurence of a specified item on the  list; to remove the first
  130. // occurence  of  a specified item on  the list; to  remove  all duplicates; to
  131. // insert a new item before or after  a specified item on  the list;  to sort a
  132. // list; to merge two lists; to perform the  intersection; union; difference or
  133. // exclusive-or of two lists.
  134. //
  135. // Unlike Common   Lisp,  the  destructive operations  do  not   come  with the
  136. // equivalent non-destructive operations  are  supported.  Most operations will
  137. // be  destructive, such that, the list  object  the message  is performed will
  138. // always  be altered.  A  non-destructive  operation  is easily  done by first
  139. // making a copy of   the  list  object  and  then executing   the  destructive
  140. // operation on that copy.
  141. //
  142. // The CoolList class implements the  notion of a  current position. This is useful
  143. // for  iterating  through the  elements of  a list.   The current position  is
  144. // maintained as a node pointer and is set or reset by all operations affecting
  145. // elements in  the  CoolList  class.  Operations to  reset,  move to the next  and
  146. // previous, find, and get the value at the current position are provided.
  147.  
  148. #ifndef BASE_LISTH        // If the CoolList not defined,
  149. #define BASE_LISTH        // indicate its done now
  150.  
  151. #ifndef STREAMH            // If the Stream support not yet defined,
  152. #if defined(DOS) || defined(M_XENIX)
  153. #include <stream.hxx>           // include the Stream class header file
  154. #else
  155. #include <stream.h>        // include the Stream class header file
  156. #endif
  157. #define STREAMH
  158. #endif
  159.  
  160. #ifndef MISCELANEOUSH        // If we have not included this file,
  161. #include <misc.h>        // include miscelaneous useful definitions.
  162. #endif
  163.  
  164.  
  165. typedef Boolean (*Compare) (void*, void*);    // Pointer to compate function
  166. typedef int (*Predicate) (void*, void*);    // Pointer to Predicate
  167. // returns -1 on less, 0 on equal and 1 on greater
  168.  
  169. class CoolList_Node;                // Forward reference class
  170.  
  171. class CoolList_Node {                // Define CoolList_Node class
  172. friend class CoolList;                // Friend class declaration
  173. public:
  174.   inline CoolList_Node*& next_node();        // Return next node pointer
  175.   friend ostream& operator<<(ostream& os, const CoolList&); // Output operator
  176.   
  177. protected:
  178.   int ref_count;                // Reference counter
  179.   CoolList_Node* next;                // Pointer to next node
  180.   
  181.   CoolList_Node();                // Constructor
  182.   virtual ~CoolList_Node();            // Delete as ~CoolList_Node<Type>
  183.   virtual void* get_data();            // Returns data element 
  184.   virtual void  set_data(void*);        // Set data element
  185. };
  186.  
  187. // next_node() -- Returns next node pointer.
  188. // Input:         None.
  189. // Output:        The next node pointer
  190.  
  191. inline CoolList_Node*& CoolList_Node::next_node () {
  192.   return this->next;
  193. }
  194.  
  195.  
  196. typedef CoolList_Node* CoolList_state;        // Curpos state for iterator
  197.  
  198. class CoolList {                // Define the CoolList class
  199. public:
  200.   CoolList() {};                // A Nil CoolList
  201.   virtual ~CoolList();                // Destructor is virtual
  202.   
  203.   inline void reset();                // Reset current position
  204.   inline Boolean next();            // Increment current position
  205.   Boolean prev();                // Decrement current position
  206.   
  207.   Boolean operator==(const CoolList& l) const;    // Equality test
  208.   inline Boolean operator!=(const CoolList& l) const; // Inequality test
  209.   
  210.   void tail(CoolList& l, int n = 1);        // Sets l to the nth tail/cdr
  211.   void last(CoolList& l, int n = 1);        // Sets l to the n last nodes
  212.   void but_last(CoolList& l, int n = 1);    // Sets l to all but n last
  213.   
  214.   void clear();                    // Removes all nodes 
  215.   inline Boolean is_empty();            // Any nodes in List?
  216.   int length();                    // Returns node count in List
  217.   int position();                // Returns current position
  218.   
  219.   Boolean search(const CoolList& l);        // SubList search
  220.   
  221.   // returns true if THIS CoolList contains the specified subList
  222.   // and sets CoolList l to a subList in THIS List starting at the 1st occurence
  223.   // of CoolList s
  224.   Boolean sublist(CoolList& l, const CoolList& s);
  225.   
  226.   void copy(const CoolList& l);            // Copy l into *this
  227.   void reverse();                // Reverses order of elements
  228.   Boolean prepend(const CoolList& l);        // Prepends l to start of List
  229.   Boolean append(const CoolList& l);        // Appends  l to end of List
  230.   
  231.   Boolean set_tail(const CoolList& l, int n = 1); // rplacd a l
  232.   Boolean remove_duplicates();              // Removes duplicate elements
  233.   
  234.   void set_intersection(const CoolList& l);    // Intersection of two Lists
  235.   void set_union(const CoolList& l);        // Union of two Lists
  236.   void set_difference(const CoolList& l);    // Difference of two Lists
  237.   void set_xor(const CoolList& l);        // XOR of two Lists
  238.   
  239.   Boolean next_intersection(const CoolList& l); // Current position intersect
  240.   Boolean next_union(const CoolList& l);    // Current position union
  241.   Boolean next_difference(const CoolList& l);    // Current position difference
  242.   Boolean next_xor(const CoolList& l);        // Current position XOR
  243.   
  244.   void describe(ostream& os);            // Describes structure of List
  245.   
  246.   friend ostream& operator<<(ostream& os, const CoolList& l); // Output 
  247.   inline friend ostream& operator<<(ostream& os, const CoolList* l); 
  248.  
  249. protected:
  250.   CoolList_Node* node_ptr;            // Pointer to first node
  251.   CoolList_Node* curpos;            // Maintains current position
  252.   CoolList_Node* prevpos;            // Performance hack to previous
  253.   Boolean traversal;                // Traversal flag for curpos
  254.   
  255.   virtual CoolList* new_list(CoolList_Node*);    // Creates a new CoolList from node
  256.   virtual CoolList_Node* insert_before_node(void* v, CoolList_Node* next_np);
  257.   virtual CoolList_Node* insert_after_node(void* v, CoolList_Node* prev_np) const;
  258.   
  259.   virtual Boolean compare_data(const void*, const void*) const;
  260.   virtual void output_data(ostream&, const CoolList_Node*) const;
  261.   
  262.   CoolList_Node* copy_nodes() const;        // Returns copy of nodes
  263.   inline void reference(CoolList_Node*);    // Increments reference count
  264.   inline void dereference(CoolList_Node*);    // Decrements reference count
  265.   // And if zero, deletes node
  266.   void CoolList::free_nodes(CoolList_Node* np); // Deletes nodes
  267.   
  268.   CoolList* operator=(const CoolList& l);    // Assignment List1 = List2;
  269.   CoolList_Node* operator[](int n);        // X = l[n];
  270.   
  271.   int position(const void* x);            // Returns 0-relative index 
  272.   virtual Boolean do_find(CoolList_Node* np, const void* x, // Used by find
  273.               CoolList_Node*& cp, CoolList_Node*& pp) const;
  274.   // returns true if THIS CoolList contains element x and 
  275.   // sets CoolList l to a subList in THIS List starting at the first occurence of x
  276.   Boolean member(CoolList& l, const void* x);
  277.   
  278.   Boolean push(const void* x);            // Adds X to head of THIS List
  279.   Boolean push_new(const void* x);        // Push(X) if not in THIS List
  280.   Boolean push_end(const void* x);        // Adds X at end of THIS List
  281.   Boolean push_end_new(const void* x);        // push_end(x) if not in List
  282.   
  283.   CoolList_Node* pop();                // Removes/returns head node
  284.   CoolList_Node* remove();            // Removes item at curpos
  285.   Boolean remove(const void* x);        // Removes first occurence
  286.   
  287.   Boolean replace(const void*, const void*);    // Replace first
  288.   Boolean replace_all(const void*,const void*); // Replace all
  289.   
  290.   void sort(Predicate f);            // Sort List using predicate
  291.   void merge(const CoolList& l, Predicate f);    // Merge List w/ sort predicate
  292.   
  293.   Boolean insert_before(const void* new_item);    // Insert item before curpos
  294.   Boolean insert_after(const void* new_item);    // Insert item after curpos
  295.   
  296.   Boolean insert_before(const void*,const void*); // Insert item before
  297.   Boolean insert_after(const void*, const void*); // Insert item after
  298.   
  299.   void value_error (const char*);        // Raise exception
  300.   void get_error (const char*, int);        // Raise exception
  301.   void before_error (const char*);        // Raise exception
  302.   void after_error (const char*);        // Raise exception
  303.   void bracket_error (const char*, int);    // Raise exception
  304.   void pop_error (const char*);            // Raise exception
  305.   void remove_error (const char*);        // Raise exception
  306.   void va_arg_error (const char*, int);        // Raise exception
  307. };
  308.  
  309.  
  310. // reference () -- Increments the reference count of a node pointer
  311. // Input:          The node pointer to be referenced.
  312. // Output:         None.
  313.  
  314. inline void CoolList::reference(CoolList_Node* np) {
  315.   if (np != NULL) np->ref_count++;
  316. }
  317.  
  318.  
  319. // dereference() -- Decrements the reference count of the node pointer and
  320. //                  deallocates storage if no longer referenced.
  321. // Input:           The node pointer to be dereferenced.
  322. // Output:          None.
  323.  
  324. inline void CoolList::dereference(CoolList_Node* np) {
  325.   if (np != NULL && --(np->ref_count) <= 0)
  326.     this->free_nodes(np);
  327. }
  328.  
  329.  
  330. // reset() -- sets current position to NULL
  331. // Input:     None.
  332. // Output:    None.
  333.  
  334. inline void CoolList::reset() {
  335.   this->curpos = NULL;
  336.   this->prevpos = NULL;
  337.   this->traversal = TRUE;
  338. }
  339.  
  340.  
  341. // next() -- Increment current position. If NULL, set it to first.
  342. // Input:    None.
  343. // Output:   TRUE or FALSE.
  344.  
  345. inline Boolean CoolList::next() {
  346.   register CoolList_Node* cp = this->curpos;
  347.   if (cp == NULL)                // Current position valid?
  348.     cp = this->node_ptr;            // Set curpos to head node
  349.   else
  350.     (cp = cp->next);                // Advance to next position
  351.   return ((this->curpos = cp) != NULL);        // Return status
  352. }
  353.  
  354.  
  355. // operator!=() -- Returns TRUE if data in THIS CoolList and the not the same
  356. // Input:          A CoolList reference.
  357. // Output:         TRUE or FALSE.
  358.  
  359. inline Boolean CoolList::operator!=(const CoolList& l) const {
  360.   return !this->operator==(l);
  361. }
  362.  
  363.  
  364. // is_empty() -- Indicates node presence in CoolList
  365. // Input:        None.
  366. // Output:       TRUE or FALSE.
  367.  
  368. inline Boolean CoolList::is_empty() {
  369.   return this->node_ptr == NULL;
  370. }
  371.  
  372. // operator<<() -- Overload output operator for CoolList objects
  373. // Input:          An output stream reference and CoolList pointer.
  374. // Output:         An output stream reference.
  375.  
  376. inline ostream& operator<<(ostream& os, const CoolList* l) {
  377.   return operator<<(os, *l);
  378. }
  379.  
  380. #endif                        // End of BASE_LISTH
  381.